package 剑指II;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-27
 **/

public class Jz085生成匹配的括号 {

    /**
     * 正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
     * <p>
     * 示例 1：
     * 输入：n = 3
     * 输出：["((()))","(()())","(())()","()(())","()()()"]
     * 示例 2：
     * 输入：n = 1
     * 输出：["()"]
     *  
     * 提示：
     * 1 <= n <= 8
     */

    private Set<String> result = new HashSet<>();
    private int n;
    private Set<String> pathSet = new HashSet<>();

    public List<String> generateParenthesis(int n) {
        this.n = n;
        this.dfs(0, 0, new StringBuilder());
        return new ArrayList<>(this.result);
    }

    private void dfs(int leftCount, int rightCount, StringBuilder path) {
        // add不存在时添加返回true
        if (!this.pathSet.add(path.toString())) {
            return;
        }
        if (leftCount > this.n || rightCount > this.n) {
            return;
        }
        if (rightCount > leftCount) {
            return;
        }
        if (rightCount == this.n) {
            this.result.add(path.toString());
            return;
        }

        path.append("(");
        this.dfs(leftCount + 1, rightCount, path);
        path.setLength(path.length() - 1);
        path.append(")");
        this.dfs(leftCount, rightCount + 1, path);
        path.setLength(path.length() - 1);
        // 双括号冗余了
//        path.append("()");
//        this.dfs(leftCount + 1, rightCount + 1, path);
//        path.setLength(path.length() - 2);

    }

}
